#include <iostream>


using namespace std;

struct Node{
    int data;
    Node *next;
    Node():data(0),next(NULL){}
    Node(int x):data(x),next(NULL){}
    Node(int x,Node *n):data(x),next(n){}
};

class CycleLinkList{
public:
    CycleLinkList():head_(NULL),tail_(NULL){
        Node *p = new Node();
        head_ = p;
        tail_ = p;
        head_->next = head_;
        tail_->next = head_;
    }
    ~CycleLinkList(){
        Node *p = head_;
        while(p){
            Node *q = p;
            p = p->next;
            delete q;
        }
    }
    void HeadInsert(int x);
    void TailInsert(int x);
    void showlinklist();
    void remove(int x);
    bool find(int x);
private:
    Node *head_;
    Node *tail_;
};

void CycleLinkList::HeadInsert(int x){
    Node *p = new Node(x);
    p->next = head_->next;
    head_->next = p;
    if(head_ == tail_){
        tail_ = p;
    }
    cout << "head_ is " << head_ << endl;
    cout << "tail_ is " << tail_ << endl;
    cout << "tail_->data is " << tail_->data << endl;
}

void CycleLinkList::TailInsert(int x){
    Node *p = new Node(x,head_);
    cout << "head_ is " << head_ << endl;
    cout << "tail_ is " << tail_ << endl;
    cout << "p is " << p << endl;
    cout << "p->next is " << p->next << endl;
    tail_->next = p;
    cout << "tail_->next is " << tail_->next << endl;
    tail_ = p;
    cout << "tail_ is " << tail_ << endl;
}

void CycleLinkList::showlinklist(){
    if (head_ == tail_){
        cout<<"empty"<<endl;
        return;
    }
    Node *p = head_->next;
    while(p != head_){
        cout<<p->data<<" ";
        p = p->next;
    }
    cout<<endl;
}

void CycleLinkList::remove(int x){
    if (head_ == nullptr) return; // 防止空链表访问
    Node *p = head_;
    Node *q = head_->next;
    cout << "head_ is " << head_ << endl;
    cout << "tail_ is " << tail_ << endl;
    while(q->next != head_){
        cout << "q is " << q << " q->data is " << q->data << endl;
        if(q->data == x){
            p->next = q->next;
            cout << "q->next is " << q->next << endl;
            if(q == tail_){
                cout << "tail_ == q " << tail_ << endl;
                tail_ = p;
            }
            delete q;
            q = p->next;
            cout << "q is " << q << endl;
        }else{
            p = q;
            q = q->next;
            cout << "q is " << q << endl;
            cout << "p is " << p << endl;
        }
    }
}

bool CycleLinkList::find(int x){
    Node *p = head_->next;
    while(p != head_){
        if(p->data == x){
            return true;
        }
        p = p->next;
    }
    return false;
}




int main()
{
    CycleLinkList list;
    list.showlinklist();

    list.HeadInsert(1);
    list.showlinklist();
    list.HeadInsert(2);
    list.showlinklist();

    list.TailInsert(3);
    list.showlinklist();
    list.TailInsert(4);
    list.showlinklist();

    if (list.find(3)){
        cout<<"find 3"<<endl;
    }else{
        cout<<"not find 3"<<endl;
    }

    list.remove(3);
    list.showlinklist();

    if (list.find(3)){
        cout<<"find 3"<<endl;
    }else{
        cout<<"not find 3"<<endl;
    }

    return 0;
}